Power of 4

Time: O(1); Space: O(1); easy

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16

Output: True

Example 2:

Input: 5

Output: False

Follow up:

  • Could you solve it without loops/recursion?

[1]:

class Solution1(object):
    def isPowerOfFour(self, n) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and \
               (n & (n - 1)) == 0 and \
               ((n & 0b01010101010101010101010101010101) == n)

[2]:

s = Solution1()
assert s.isPowerOfFour(16) == True
assert s.isPowerOfFour(5) == False

[3]:

class Solution2(object):
    def isPowerOfFour(self, n) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        while n and not (n & 0b11):
            n >>= 2
        return (n == 1)

[4]:

s = Solution2()
assert s.isPowerOfFour(16) == True
assert s.isPowerOfFour(5) == False

[5]:

class Solution3(object):
    def isPowerOfFour(self, n) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        n = bin(n)
        return True if n[2:].startswith('1') and \
                    len(n[2:]) == n.count('0') and \
                    n.count('0') % 2 \
                    and '-' not in n \
                    else False

[6]:

s = Solution3()
assert s.isPowerOfFour(16) == True
assert s.isPowerOfFour(5) == False